Méthodes de Monte Carlo

6. Prédiction avec échantillonnage préférentiel (Importance Sampling)

6.4. Algorithme itératif de prédiction

La prédiction en utilisant l'échantillonnage préférentiel peut être réalisée de manière itérative, c'est-à-dire épisode par épisode. On va s'intéresser ici à l'algorithme utilisé dans le cadre de l'utilisation de l'échantillonnage préférentiel pondéré.

Supposons que nous ayons une séquence de revenus $G_1, G_2,...,G_{n-1}$ pour un état $s$ obtenus avec les trajctoires de la police d'exploration $b$ et les ratios d'échantillonnages préférentiels correspondants $W_1, W_2, ..., W_{n-1}$ (${W_i} = {\rho _{{t_i}:T({t_i}) - 1}}$). Notre objectif est d'estimer la valeur de l'état $s$ sous la stratégie cible $\pi$:

$$\large{V_n}(s)_\pi = \frac{{\sum\limits_{k = 1}^{n - 1} {{W_k}{G_k}} }}{{\sum\limits_{k = 1}^{n - 1} {{W_k}} }}, \quad n>2$$

En posant ${C_n} = \sum\limits_{k = 1}^n {{W_k}}$, on peut obtenir une relation de récurrence sur les $V_n(s)_\pi$:

$\large{V_{n + 1}} = \frac{{\sum\limits_{k = 1}^n {{W_k}{G_k}} }}{{\sum\limits_{k = 1}^n {{W_k}} }} = \frac{{\sum\limits_{k = 1}^{n - 1} {{W_k}{G_k} + {W_n}{G_n}} }}{{{C_n}}} = \frac{{{W_n}{G_n}}}{{{C_n}}} + \frac{{\sum\limits_{k = 1}^{n - 1} {{W_k}{G_k}\sum\limits_{k = 1}^{n - 1} {{W_k}} } }}{{{C_n}\sum\limits_{k = 1}^{n - 1} {{W_k}} }}$

$\large{V_{n + 1}} = \frac{{{W_n}{G_n}}}{{{C_n}}} + \frac{{{V_n}}}{{{C_n}}}\sum\limits_{k = 1}^{n - 1} {{W_k}} = \frac{{{W_n}}}{{{C_n}}}\left( {{G_n} + \frac{{{C_{n - 1}}}}{{{W_n}}}{V_n}} \right)$

$\large{V_{n + 1}} = \frac{{{W_n}}}{{{C_n}}}\left( {{G_n} + \left( {\frac{{{C_n} - {W_n}}}{{{W_n}}}} \right){V_n}} \right) = \frac{{{W_n}}}{{{C_n}}}\left( {{G_n} - {V_n}} \right) + {V_n}$

L'algorithme que nous devons mettre en place doit donc effectuer les opérations de récurrences:

• Échantillonnage préférentiel pondéré:

$\quad\quad\circ$ Équation récurente de la valeur de l'état $S_t$ en suivant la stratégie $\pi$:

$\large\quad\quad\quad\quad{V_{n + 1}}{\left( {{S_t}} \right)_\pi } = \frac{{{W_n}\left( {{S_t}} \right)}}{{{C_n}\left( {{S_t}} \right)}}\left( {{G_n}{{\left( {{S_t}} \right)}_b} - {V_n}{{\left( {{S_t}} \right)}_\pi }} \right) + {V_n}{\left( {{S_t}} \right)_\pi }\quad\quad,{\rm{ }}n \ge 1$

$\quad\quad\circ$ Ratio d'échantillonage de l'épisode n, en partant de l'état $S_t$:

$\large\quad\quad\quad\quad{W_n}\left( {{S_t}} \right) = {\rho _{t:T - 1}}\left( {{S_t}} \right) = \prod\limits_{k = t}^{T - 1} {\frac{{\pi \left( {{A_k}|{S_k}} \right)}}{{b\left( {{A_k}|{S_k}} \right)}}} {\rm{ }}$

$\quad\quad\circ$ Somme des ratios d'échantillonage de l'épisode 1 à n:

$\large\quad\quad\quad\quad{C_n}\left( {{S_t}} \right) = \sum\limits_1^n {{W_n}\left( {{S_t}} \right)}$

$\quad\quad\circ$ Revenus de l'épisode n, en partant de l'état $S_t$ jusqu'à l'état $S_T$ mais en "remontant le calcul":

$\large\quad\quad\quad\quad{G_n}\left( {{S_{t \in \left[ {t:T} \right]}}} \right) = \sum\limits_{k = t}^{T - 1} {{\gamma ^{t - k}}{R_{k + 1}}}=\sum\limits_{k = T - 1}^t {{\gamma ^{T - 1 - k}}{R_{k + 1}}}$

$\large\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad= {R_T} + \sum\limits_{k = T - 2}^t {{\gamma ^{T - 1 - k}}{R_{k + 1}}}$

$\large\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad={R_T} + \gamma \sum\limits_{k = T - 2}^t {{\gamma ^{T - k}}{R_{k + 1}}}$

$\large\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad={R_T} + \gamma {G_n}\left( {{S_{t \in \left[ {t:T - 1} \right]}}} \right)$

$\large\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad={R_T} + \gamma {G_n}\left( {{S_{t \in \left[ {T - 1:t} \right]}}} \right)$

avec $C_0=0$ et $V_1$ arbitraire.

Algorithme